package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/7/26 22:07
 * 二叉树的镜像
 * 算法：递归、层次遍历
 */
public class BM33 {

    public TreeNode Mirror(TreeNode pRoot) {
        // write code here
        if (pRoot == null) return null;
        TreeNode right = pRoot.right;
        pRoot.right = Mirror(pRoot.left);
        pRoot.left = Mirror(right);
        return pRoot;
    }

    public TreeNode MirrorStack(TreeNode pRoot) {
        if (pRoot == null) return null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(pRoot);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
            TreeNode left = node.left;
            node.left = node.right;
            node.right = left;
        }
        return pRoot;
    }

}
